package com.zhao.test2;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.zhao.test2.RoadLine;

public class MyWeightedGraph {
	private class Vertex implements Comparable<Vertex> {
		private String vertexLabel;// 顶点标识
		private List<Edge> adjEdges;// 顶点的所有邻接边(点)
		private int dist;// 顶点到源点的最短距离
		private Vertex preNode;// 前驱顶点

		public Vertex(String vertexLabel) {
			this.vertexLabel = vertexLabel;
			adjEdges = new LinkedList<Edge>();
			dist = Integer.MAX_VALUE;
			preNode = null;
		}

		@Override
		public int compareTo(Vertex v) {
			if (this.dist > v.dist)
				return 1;
			else if (this.dist < v.dist)
				return -1;
			return 0;
		}
	}

	private class Edge {
		private int weight;// 边的权值(带权图)
		private Vertex endVertex;

		public Edge(int weight, Vertex endVertex) {
			this.weight = weight;
			this.endVertex = endVertex;
		}
	}

	private Map<String, Vertex> weightedGraph;// 存储图(各个顶点)
	private Vertex startVertex;// 单源最短路径的起始顶点
	private Vertex endVertex;// 单源最短路径的起始顶点
	private StringBuilder sb = new StringBuilder();

	// 图的信息保存在文件中,从文件中读取成字符串graphContent
	// public MyWeightedGraph(String graphContent) {
	// weightedGraph = new LinkedHashMap<String, MyWeightedGraph.Vertex>();
	// buildGraph(graphContent);//解析字符串构造图
	// }
	public MyWeightedGraph(List<RoadLine> roadLines) {
		// TODO Auto-generated constructor stub
		weightedGraph = new LinkedHashMap<String, MyWeightedGraph.Vertex>();
		buildGraph(roadLines);// 解析字符串构造图
	}

	private void buildGraph(List<RoadLine> roadLines) {
		// String[] lines = graphContent.split("\n");

		String startNodeLabel, endNodeLabel;
		Vertex startNode, endNode;
		int weight;

		for (RoadLine roadLine : roadLines) {
			startNodeLabel = String.valueOf(roadLine.getStart());
			endNodeLabel = String.valueOf(roadLine.getEnd());
			weight = Integer.valueOf(roadLine.getLength());

			endNode = weightedGraph.get(endNodeLabel);
			if (endNode == null) {
				endNode = new Vertex(endNodeLabel);
				weightedGraph.put(endNodeLabel, endNode);
			}

			startNode = weightedGraph.get(startNodeLabel);
			if (startNode == null) {
				startNode = new Vertex(startNodeLabel);
				weightedGraph.put(startNodeLabel, startNode);
			}
			Edge e = new Edge(weight, endNode);
			// 对于无向图而言,起点和终点都要添加边
			// endNode.adjEdges.add(e);
			startNode.adjEdges.add(e);
		}

	}

	private void dijkstra() {
		BinaryHeap<Vertex> heap = new BinaryHeap<MyWeightedGraph.Vertex>();
		init(heap);// inital heap

		while (!heap.isEmpty()) {
			Vertex v = heap.deleteMin();
			List<Edge> adjEdges = v.adjEdges;// 获取v的所有邻接点
			for (Edge e : adjEdges) {
				Vertex adjNode = e.endVertex;
				// update
				if (adjNode.dist > e.weight + v.dist) {
					adjNode.dist = e.weight + v.dist;
					adjNode.preNode = v;
				}
			} // end for

			// 更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
			heap.buildHeap();
		}

	}

	private void init(BinaryHeap<Vertex> heap) {
		startVertex.dist = 0;// 源点到其自身的距离为0
		for (Vertex v : weightedGraph.values()) {
			heap.insert(v);
		}
	}

	public void showDistance() {
		for (Vertex v : weightedGraph.values()) {
			printPath(v);
			System.out.println();
			System.out.println("顶点 " + v.vertexLabel + "到源点" + startVertex.vertexLabel + " 的距离: " + v.dist);
		}
	}

	// 打印源点到 end 顶点的 最短路径
	private void printPath(Vertex end) {
		if (end.preNode != null)
			printPath(end.preNode);
		System.out.print(end.vertexLabel + "--> ");
		sb.append(end.vertexLabel + "-");
	}

	// ============下面是为了更加的适应我们项目需求而修改的方法
	public StepResult getMinStep(int start, int end) {
		StepResult step=new StepResult();
		if (weightedGraph != null) {
			// 设置起始点
			startVertex = weightedGraph.get(String.valueOf(start));
			endVertex = weightedGraph.get(String.valueOf(end));
			
			dijkstra();
			printPath(endVertex);
			System.out.println();
		}
        step.setMinstep(sb.toString().substring(0, sb.toString().length()-1));
        step.setLength(endVertex.dist);
		return step;
	}

}